문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 동적 계획법 (문단 편집) ==== 재귀함수 형태의 피보나치 수열 ==== 피보나치 수열은 다음과 같이 [[재귀함수]]의 형태(Recursive Form)로 표현된다. {{{f(0) = 1 f(1) = 1 f(n) = f(n-1) + f(n-2) when n > 1}}} 이 수학적인 정의는 매우 깔끔하지만, 실제로 컴퓨터가 계산하기엔 매우 부적합한 형태이다. 위 정의를 그대로 C언어로 구현하면 아래와 같다. {{{#!syntax cpp int f(unsigned int n) { if(n <= 1) return 1; else return f(n-1)+f(n-2); } }}} C언어를 배우면 왜 문제인지 알 수 있다. 함수가 호출되면 프로그램 메모리의 [[스택(자료구조)|스택]](Stack)이라는 곳에 데이터가 쌓이게 된다. 그 함수의 실행이 끝났을 때 다시 메모리가 해제되는 방식인데, 이 말인 즉슨 함수가 계속 호출되면 메모리에 쌓이는 것들이 계속 증가한다는 소리다! 여기서 재귀적 피보나치 함수의 문제가 드러난다. 5번째 피보나치 수열을 구하기 위해선 다음 그림과 같이 총 15번의 함수 호출이 발생한다. [[파일:5-23-3.png|width=600]] 숫자가 작을 때는 그나마 괜찮지만, 숫자가 조금만 커져도 시간 복잡도와 공간 복잡도가 지수 스케일로 폭발한다! (이런 걸 Exponential Explosion이라고 한다) 시간 복잡도야 시간을 많이 들이면 견딜 수 있다 해도, 공간 복잡도의 경우 스택 오버플로우가 발생해 프로그램이 튕겨버린다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기